#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
struct ListNode {
    int val;
    struct ListNode* next;
};

struct Node {
    int val;
    struct Node* next;
    struct Node* random;
    
};

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* low = head, * fast = head;
    while (fast != NULL && fast->next != NULL) {
        low = low->next;
        fast = fast->next->next;
        if (low == fast)
            break;
    }
    if (fast == NULL || fast->next == NULL)
        return NULL;
    struct ListNode* cur = head;
    while (cur != low) {
        cur = cur->next;
        low = low->next;
    }
    return cur;
}

struct Node* copyRandomList(struct Node* head) {
    struct Node* copy = NULL, * cur = head;
    while (cur != NULL) {
        copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
        cur = copy->next;
    }
    cur = head;
    while (cur != NULL) {
        copy = cur->next;
        if (cur->random == NULL) {
            copy->random = NULL;
        }
        else {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }
    struct Node* copyhead = NULL, * copytail = NULL;
    cur = head;
    while (cur) {
        copy = cur->next;
        if (copyhead == NULL) {
            copyhead = copytail = copy;
        }
        else {
            copytail->next = copy;
            copytail = copytail->next;
        }
        cur = copy->next;
    }
    return copyhead;
}

int main() {
    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));

    struct ListNode* N1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* N2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* N3 = (struct ListNode*)malloc(sizeof(struct ListNode));

    n1->val = 1;
    n2->val = 2;
    n3->val = 3;
    n4->val = 4;
    n5->val = 5;

    N1->val = 2;
    N2->val = 4;
    N3->val = 6;

    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n5;
    n5->next = NULL;

    N1->next = N2;
    N2->next = N3;
    N3->next = NULL;

    struct ListNode* cur = n1;

    while (cur) {
        printf("%d->", cur->val);
        cur = cur->next;
    }
    printf("NULL\n");



    //struct ListNode* head = detectCycle(n1);
    struct ListNode* head = copyRandomList(n1);

    //printf("%d->", head->val);

    while (head) {
        printf("%d->", head->val);
        head = head->next;
    }
    printf("NULL\n");

    return 0;
}